package com.wwy.arithmetic.suanfa;

import com.wwy.arithmetic.suanfa.entry.TreeNode;
import sun.reflect.generics.tree.Tree;

import java.util.*;

/**
 * 二叉树后序遍历
 */
public class TreeHouXuBianLi {

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2 = new TreeNode(1);
        TreeNode treeNode3 = new TreeNode(2);
//        TreeNode treeNode4 = new TreeNode(4);
//        TreeNode treeNode5 = new TreeNode(5);
//        TreeNode treeNode6 = new TreeNode(6);
//        TreeNode treeNode7 = new TreeNode(7);
        treeNode1.setLeft(treeNode2);
        treeNode1.setRight(treeNode3);
//        treeNode2.setLeft(treeNode4);
//        treeNode2.setRight(treeNode5);
//        treeNode3.setLeft(treeNode6);
//        treeNode3.setRight(treeNode7);
        List<Integer> numbers = getStackNum(treeNode1, new ArrayList<>());
        if (numbers.size() > 0) {
            List<Integer> list = new ArrayList<>();
            for (int i = numbers.size() - 1; i >= 0; i--) {
                list.add(numbers.get(i));
            }
            for (Integer integer : list) {
                System.out.println("integer = " + integer);
            }
        }
    }

    /**
     * 使用普通的递归解决
     *
     * @param treeNode
     * @param list
     * @return
     */
    static List<Integer> getNums(TreeNode treeNode, List<Integer> list) {
        if (treeNode == null) {
            return list;
        }
        list.add(treeNode.getVal());
        getNums(treeNode.getRight(), list);
        getNums(treeNode.getLeft(), list);
        return list;
    }

    /**
     * 使用栈解决
     *
     * @param treeNode
     * @param list
     * @return
     */
    static List<Integer> getStackNum(TreeNode treeNode, List<Integer> list) {
        Deque<TreeNode> deque = new LinkedList<>();
        while (!deque.isEmpty() || treeNode != null) {
            while (treeNode != null) {
                deque.push(treeNode);
                list.add(treeNode.getVal());
                treeNode = treeNode.getRight();
            }
            treeNode = deque.pop();
            treeNode = treeNode.getLeft();
        }
        return list;
    }
}
